package DataStr.homework04.h2;

public class QuickSort {
    public static void quickSort(int[]arr,int low,int high){
        if(low<high) {//递归的结束条件
            //获取基准元素的索引
            int p = partition(arr, low, high);
            //递归对左右两边部分进行排序
            quickSort(arr, low, p - 1);//基准左边的部分
            quickSort(arr, p + 1, high);//基准右边的部分
        }
    }
    public static int partition(int[]arr,int low,int high){
        //选择基准元素，这里选择最右边的元素作为基准元素
        int p=arr[high];
        int i=low-1;//i用于标记小于基准的区域
        //遍历数组将小于等于最右边元素的元素移到左边
        for(int j=low;j<high;j++){
            if(arr[j]<=p){
                i++;
               swap(arr,i,j);
            }
        }
        swap(arr,i+1,high);
        return i+1;//返回基准元素的新位置
    }
    public static void swap(int[]arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    public static void print(int[]arr){
        for(int i:arr){
            System.out.print(i+" ");
        }
        System.out.println();
    }
    public static void main(String[]args){
        int[]arr={49, 38, 65, 97, 76, 13, 27, 49};
        System.out.print("排序前的数组为:");
        print(arr);
        quickSort(arr,0,arr.length-1);
        System.out.print("排序后的数组为:");
        print(arr);
    }
}